In multithreaded programs, several threads can be involved in the processing of a single request and a bounded buffer instance can serve to decouple the operation of threads with different roles in the request handling. For example, few (for example, one to three) threads poll requests from a network socket and insert them at one end into a bounded buffer. These threads are referred to as “putters.” At the other end of the buffer, a plurality of worker threads take requests from the buffer and service them. These threads are referred to as “takers.”
For example, a bounded buffer may be implemented as a circular array with two indices, takeIndex and putIndex, and two counters, numberOfUsedSlots and numberOfEmptySlots. The two counters indicate to takers and putters whether or not the buffer is empty or full, respectively. The buffer is protected by two locks. One lock primarily protects numberOfUsedSlots as well as take-related variables of the buffer, i.e. the takeIndex variable and the next used slot in the buffer. The other lock protects numberOfEmptySlots as well as put-related variables of the buffer, i.e. the putIndex variable and the next empty slot in the buffer.
In operation, both putters and takers need to acquire the two locks in reverse order but in sequence (hence no deadlock due to circular wait). For example, a put operation first acquires the put-related lock and if the buffer is not fall, it inserts an object, decrements numberOfEmptySlots, releases the put-related lock and then acquires the take-related lock and increments numberOfUsedSlots, notifies any takers that are waiting for the buffer to be not empty and then releases the take-related lock. If the putter finds the buffer full, it waits on the put-related lock for notification when the buffer becomes not full. Similar steps of acquiring the locks are performed by takers when extracting a request from the buffer.
A significant source of contention and high latency in this implementation is that both putters and takers acquire both locks even when the buffer is neither empty nor full. Moreover, the critical locks may be inflated and deflated in case putter or taker threads have to wait. Accordingly, an improved mechanism for inserting and extracting from a buffer is desirable.